| 翻訳と辞書 |
| graph traversal ： ウィキペディア英語版 |
graph traversal
In computer science, graph traversal is the problem of visiting all the nodes in a graph in a particular manner, updating and/or checking their values along the way. Tree traversal is a special case of graph traversal.
==Redundancy==
Unlike tree traversal, graph traversal may require that some nodes be visited more than once, since it is not necessarily known before transitioning to a node that it has already been explored. As graphs become more dense, this redundancy becomes more prevalent, causing computation time to increase; as graphs become more sparse, the opposite holds true.
Thus, it is usually necessary to remember which nodes have already been explored by the algorithm, so that nodes are revisited as infrequently as possible (or in the worst case, to prevent the traversal from continuing indefinitely). This may be accomplished by associating each node of the graph with a "color" or "visitation" state during the traversal, which is then checked and updated as the algorithm visits each node. If the node has already been visited, it is ignored and the path is pursued no further; otherwise, the algorithm checks/updates the node and continues down its current path.
Several special cases of graphs imply the visitation of other nodes in their structure, and thus do not require that visitation be explicitly recorded during the traversal. An important example of this is a tree, during a traversal of which it may be assumed that all "ancestor" nodes of the current node (and others depending on the algorithm) have already been visited. Both the depth-first and breadth-first graph searches are adaptations of tree-based algorithms, distinguished primarily by the lack of a structurally determined "root" node and the addition of a data structure to record the traversal's visitation state.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「graph traversal」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|